//https://leetcode.cn/problems/sliding-window-maximum/
package codeRandomThoughts.Test239滑动窗口最大值;

import java.util.Arrays;

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        MaxThree maxThree = new MaxThree(k);
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; i++) {
            if (i + 1 > k) {
                maxThree.remove(nums[i - k]);
                System.out.println("移除了" + nums[i - k]);
            }
            maxThree.add(nums[i]);
            if (i + 1 >= k) {
                res[i + 1 - k] = maxThree.max();
                System.out.println("i=" + i + "时窗口最大值为" + maxThree.max());
            }
        }

        return res;
    }
}

/**
 * 一定要确保此处逻辑正确
 */
class MaxThree {
    int[] nums;

    public MaxThree(int k) {
        nums = new int[k];
        Arrays.fill(nums,Integer.MIN_VALUE);
    }

    public int add(int n) {
        for (int i = 0; i < nums.length; i++) {
            if (n >= nums[i]) {
                //nums总体往右移动
                for (int j = nums.length - 1; j > i; j--) {
                    nums[j] = nums[j - 1];
                }

                //nums[i]=n
                nums[i] = n;
                System.out.println("窗口内值:" + nums);
                return n;
            }
        }
        return -1;
    }

    /**
     * 这样移动整个数组太超时了,应该换成链表?
     * @param n
     * @return
     */
    public boolean remove(int n) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == n) {
                for (int j = i; j < nums.length-1; j++) {
                    nums[j]=nums[j+1];
                }
                nums[nums.length-1]=Integer.MIN_VALUE;
                return true;
            }
        }
        return false;
    }

    public int max() {
        return nums[0];
    }
}